SPDZ 学习笔记-part1

安全多方计算（SecureMultipartyComputation,MPC）旨在解决多个参与方之间的安全计算问题，目的是使各参与方在不知晓其他参与方输入信息的前提下完成计算，并可保证计算过程不泄漏输入信息。我们将分为两部分整理SPDZ协议，第一部分主要介绍基本概念和协议主要流程，下一部分介绍协议详细流程。

1

概要

SPDZ是一种MPC计算的协议框架，基于同态加密、秘密共享等技术实现安全多方计算，相关内容引自参考文献[1].

• SPDZ主要包括两个阶段，离线阶段（预计算）主要基于同态加密生成在现阶段需要的参数，在线阶段主要基于秘密共享完成各种计算。
• SPDZ可以计算有限域中的任何计算。
• SPDZ 满足 UC 安全框架下的静态恶意敌手(static adaptive adversay)攻击模型，即 n 个参与方中，即使最多 n-1 个参与方恶意违反协议或者合谋。
• SPDZ使用Message Authentication Code (MAC)，检测参与方是否诚实地进行计算，MAC参数在离线阶段生成。
• SPDZ不检测哪个参与方为恶意参与方，在检测到协议被违反情况即停止协议运行而防止数据泄漏。

2

安全模型安全多方计算安全模型一般采用Universally composable（UC）模型[2]，按照攻击者能力可以划分为半诚实、恶意参与者，按照恶意参与者的门限可以划分为多数诚实、多数恶意协议。按照攻击者能力：

• 半诚实模型：各参与方在计算过程中完全遵从 MPC 协议，既不会违反协议篡改数据也不会多个参与方之间进行合谋。
• 恶意模型：攻击者允许随意篡改协议，可以联合他人进行合谋攻击。

按照攻击者门限：

• 多数诚实：恶意参与者不超过总参与方一半。
• 多数恶意：恶意参与者至多可以有个（总参与方为）。

SPDZ协议满足Universally composable（UC）框架下的静态恶意敌手(static adaptive adversay)攻击模型，最多允许个恶意参与方。
3

基本定义

秘密分享值表示方法：共有两种表示方法,和，第一种主要用于表示输入的秘密分享值，第二种则主要用于表示全局密钥和随机数等参数。1.表示方法 有限域中的值的秘密分享值表示方法为：

其中，，

各参与方持有,为公开值，为全局MAC密钥。

秘密分享值计算具有以下性质：

其中，

2.表示方法

的秘密分享值表示方法为：

其中，，，各参与方持有

，为各参与方的密钥，主要验证MAC密钥和随

机数秘密分享值的MAC验证。

MAC密钥MAC密钥 全局MAC密钥秘密分享值表示方法为，由于每个参与方持有，因此各参与方可通过验证MAC密钥。为了打开，参与方将发送给，校验是否成立。三元组及乘法运算加法计算相对直接，直接利用秘密分享值的性质，计算加法，即可得到结果，。乘法计算需要借助三元组（Beaver Triple[3]），三元组在离线阶段生成，表示为,,，且满足，由于在实际生成三元组过程中可能会引入误差，因此，需要额外“消耗”(sacrificing)一组三元组,,，用于校验三元组。给定一组三元组,,，设输入为则乘法可按以下方法计算：首先打开得到，打开得到，然后计算。正确性验证：4

SPDZ协议

SPDZ协议主要包括离线阶段和在线阶段。

离线阶段

离线阶段需要用到同态加密技术，产生的辅助数据包括：

• 多元乘法三元组的秘密分享值；

• 随机数秘密分享值；
• 全局MAC密钥。

这些辅助信息和在线计算阶段的输入数据无关，因此可以提前进行计算。

以全局MAC密钥为例，介绍离线阶段生成参数过程：

1. 各参与方联合生成同态加密公钥和私钥，以 BGV 方案[4]为例，私钥和公钥具有线性特性，因此解密过程中各方可利用进行部分解密，然后把解密结果汇总得到最终明文结果，解密过程中不泄漏各自部分的私钥； 2. 各参与方生成随机数，然后利用进行同态加密得到密文(表示的同态密文)，并将密文发送给其他参与方; 3. 各参与方汇总得到，利用私钥进行联合解密，联合解密过程中会加入一个随机数进行混淆，然后reShare得到。

离线阶段详细协议见下一part。

在现阶段

在现阶段主要完成计算以及中间值和结果的MAC校验等，基础计算主要包括加法、乘法等。在现阶段主要过程如下：

1. 初始化。准备全局MAC密钥，随机数秘密分享值，乘法三元组,,等参数。

2. 输入阶段。设参与方的输入为，向打开[r]，然后广播，各参与方计算。输入阶段主要是将输入值分片，产生对应的秘密分享值。

3. 加法计算。设输入为，计算。 

4. 乘法计算。设输入为，则计算分为两步：1）使用三元组 校验,；2）计算。 

5. 输出阶段。再输出最终结果前，需要对中间值、结果进行MAC校验，SPDZ 协议 MAC 验证时为了提高效率，可以在打开多个秘密分享值后通过一次MAC批量校验。

在线阶段详细协议见下一part。

5

参考文献

[1] I Damgård, Pastro V , Smart N , et al. Multiparty Computation from Somewhat Homomorphic Encryption[C]// Springer-Verlag New York, Inc. Springer-Verlag New York, Inc. 2012.

[2] R. Canetti, Y. Lindell, R. Ostrovsky, and A. Sahai. Universally composable two-party and multi-party secure computation. In STOC, pages 494–503, 2002.

[3] Beaver. Efficient multiparty protocols using circuit randomization. In J. Feigenbaum, editor, CRYPTO, volume 576 of Lecture Notes in Computer Science, pages 420–432. Springer, 1991.

[4] Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. In ITCS, pages 309–325. ACM, 2012.

本文来自知乎作者：小明原文链接：https://zhuanlan.zhihu.com/p/533900089

END

往期推荐

横向联邦学习下隐私保护安全聚合：问题，方法，与展望
同态加密开源框架整理
为下一代可信计算设计更好的数据中心（arxiv）
基于隐私保护的联邦推荐算法综述

欢迎投稿邮箱：[e-mail]参与更多讨论，请添加小编微信加入交流群